package 动态规划;

public class 机器人找位置 {
    /**
     * 给定机器人的值，在指定步数中就可以到达目标位置
     *
     * @param cur  机器人当前位置
     * @param rest 机器人还需要rest步取走
     * @param aim  最终的目标位置
     * @param N    总共有多少位置
     * @return 返回共有集中方法
     */
    public static int process(int cur, int rest, int aim, int N) {
        //终止条件，rest == 0 cur == aim，返回1，表示找到了一种方法
        if (rest == 0) {
            return cur == aim ? 1 : 0;
        }
        //走到这里说明，至少还有1没走
        if (cur == 1) {//如果在第一个位置，那么就只能向第二个位置移动
            return process(2, rest - 1, aim, N);
        }
        if (cur == N) {//如果在最后一个位置，那么就只能向倒数第二个位置移动
            return process(N - 1, rest - 1, aim, N);
        }
        //否则在中间位置，就返回向左边走和向右边走方法的和
        return process(cur - 1, rest - 1, aim, N) + process(cur + 1, rest - 1, aim, N);
    }

    /**
     * 给定机器人的值，在指定步数中就可以到达目标位置
     *
     * @param cur  机器人当前位置
     * @param rest 机器人还需要rest步取走
     * @param aim  最终的目标位置
     * @param N    总共有多少位置
     * @param dp   使用一个二位数组来保存计算过的方法
     * @return 返回共有集中方法
     */
    public static int process1(int cur, int rest, int aim, int N, int[][] dp) {
        //如果数组中当前位置的已经被计算过了，直接返回
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        int ans = 0;

        //终止条件，rest == 0 cur == aim，返回1，表示找到了一种方法
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
        } else if (cur == 1) {//如果在第一个位置，那么就只能向第二个位置移动
            ans = process(2, rest - 1, aim, N);
        } else if (cur == N) {//如果在最后一个位置，那么就只能向倒数第二个位置移动
            process(N - 1, rest - 1, aim, N);
        } else {
            ans = process(cur - 1, rest - 1, aim, N) + process(cur + 1, rest - 1, aim, N);
        }
        dp[cur][rest] = ans;
        return ans;
    }

    public static int process2(int cur, int rest, int aim, int N) {
        int[][] dp = new int[N + 1][rest + 1];
        dp[aim][0] = 1;//第0列填好
        for (int i = 1; i <= rest; i++) {
            dp[1][i] = dp[2][i - 1];
            for (int j = 2; j < N; j++) {
                dp[j][i] = dp[j - 1][i - 1] + dp[j + 1][i - 1];
            }
            dp[N][i] = dp[N - 1][i - 1];
        }
        return dp[cur][rest];
    }


    public static void main(String[] args) {
        int i = process(2, 6, 4, 5);
        System.out.println(i);
        int[][] dp = new int[5][5];
        for (int j = 0; j <= 4; j++) {
            for (int k = 0; k <= 4; k++) {
                dp[j][k] = -1;
            }
        }
//        System.out.println(process1(2, 6, 4, 5, dp));
        System.out.println(process2(2, 6, 4, 5));
    }
}
